
from collections import deque
import sys
class Node :
    def __init__(self, data: int): 
        self.value = data
        self.left = None
        self.right = None

'''
是否满二叉树, 树型dp解法
返回值（nodes, height）
'''
def f(head: Node) -> tuple:
    if not head: return 0, 0
    left_info = f(head.left)
    right_info = f(head.right)

    return (left_info[0]+right_info[0] + 1), (max(left_info[1], right_info[1]) + 1)

def is_full(head: Node) -> bool:
    if not head: return True
    nodes, height = f(head)
    return nodes == ((1 << height) - 1)

'''
判断一棵树是否是二叉搜索树
当把左边界都压入，弹出就是：先弹左再弹中
'''

# 返回值（isBST, imax, imin）
def process(head: Node) -> tuple: # 树型dp解法
    if not head: return None
    left_info = process(head.left)
    right_info = process(head.right)
    imin = imax = head.value
    if left_info : 
        imax = max(imax, left_info[1])
        imin = min(imin, left_info[2])
    if right_info:
        imax = max(imax, right_info[1])
        imin = min(imin, right_info[2])
    isBST = True
    if left_info and (not left_info[0] or left_info[1] >= head.value):  #左树不是bst, 或者左树的最大值>= 当前值
        isBST = False
    if right_info and (not right_info[0] or right_info[2] <= head.value):
        isBST = False
    return isBST, imax, imin
def isBST(head: Node)-> bool:
    return process(head)[0]


def isBST1(head: Node)-> bool: # 非递归版
    if not head :return True
    if head:
        stack = []
        prevalue = -sys.maxsize # 系统最小
        while len(stack) > 0 or head :
            if head: # 先把左边都遍历完
                stack.append(head)
                head = head.left
            else :
                head = stack.pop()  # 前面看到，head为空，从栈拿一个节点，打印，当前节点变到右，
                if prevalue >= head.value: return False
                else : prevalue = head.value
                head = head.right  
    return True

prevalue = -sys.maxsize # 系统最小
def isBST2(head: Node)-> bool: # 中序遍历的时候，是升序的
    if not head :return True
    left_isBST = isBST(head.left)
    if not left_isBST: return False
    global prevalue
    if prevalue >= head.value: return False
    else : prevalue = head.value
    return isBST(head.right)


def isBST3(head: Node) -> bool: #非递归版，并且不使用额外空间
    if not head :return True
    res, pre, cur1 = True, None, head
    while cur1  :
        cur2 = cur1.left
        if cur2 :
            while cur2.right and cur2.right != cur1 :
                cur2 = cur2.right
            if not cur2.right :
                cur2.right = cur1
                cur1 = cur1.left
                continue
            else :
                cur2.right = None
        if pre and pre.value > cur1.value:
            res = False
        pre = cur1
        cur1 = cur1.right
    return res


#判断是否完全二叉树
def isCBT(head: Node) -> bool:
    if not head : return True
    queue = deque()
    leaf, l, r = False, None, None
    queue.append(head)
    #按层遍历
    while len(queue) > 0:
        head = queue.popleft()
        l = head.left
        r = head.right
        #(leaf and (l or r)) 叶子节点，但是有左孩子or右孩子,false
        #(not l and r) 有右孩子没有左孩子 false
        if (leaf and (l or r)) or (not l and r) : return False
        if l : queue.append(l) 
        if r : 
            queue.append(r)
        else:
            leaf = True # 开启了叶子节点遍历阶段(1. 左右都没有，2. 有左没右)
    return True

#打印二叉树 
def getSpace(num: int) -> str:
    # return f'|{" "*num}|'
    return f'|{" "*num}|'
def printInOrder(head: Node, height: int, to: int, length: int):
    if not head :  return
    printInOrder(head.right, height + 1, "v", length)
    val = to + str(head.value) + to
    lenM = len(val)
    lenL = (length-lenM) >> 1
    lenR = length - lenM - lenL
    val = getSpace(lenL) + val + getSpace(lenR)
    print(getSpace(height * length) + val)
    printInOrder(head.left, height + 1, "^", length)
def printTree(head: Node) :
    print("Binary Tree:")
    printInOrder(head, 0, "H", length=17)

def main():
    head =  Node(4)
    head.left =  Node(2)
    head.right =  Node(6)
    head.left.left =  Node(1)
    head.left.right =  Node(3)
    head.right.left =  Node(5)
    printTree(head)
    print(isBST(head))
    print(isCBT(head))
    print(is_full(head))
main()


'''
判断是否是平衡二叉树
'''
class Node :
    def __init__(self, data: int): 
        self.value = data
        self.left = None
        self.right = None
#返回值(is_balance, height)
def process(head: Node) -> tuple:
    if not head : return True, 0
    left_res = process(head.left)
    right_res = process(head.right)
    height = max(left_res[1], right_res[1]) + 1 #当前树的高度
    is_balance = left_res[0] and right_res[0] and (abs(left_res[1] - right_res[1]) < 2)
    return is_balance, height
def isBalance(head: Node) -> bool:  # 使用树型dp的方式
    return process(head)[0]



def getHeight(head: Node, level: int, res: list)-> int:
    if not head : return level
    lH = getHeight(head.left, level + 1, res) # 左子树的高度， 
    if not res[0] :return level # 不平衡，退出
    rH = getHeight(head.right, level + 1, res)
    if not res[0] :return level
    if abs(lH - rH) > 1: res[0] = False # 不平衡
    return max(lH, rH)
def isBalance1(head: Node) -> bool:
    res = [None]*1
    res[0] = True
    getHeight(head, 1, res) # 返回树高度，head是第1层
    return res[0]

def main():
    head =  Node(1)
    head.left =  Node(2)
    head.right =  Node(3)
    head.left.left =  Node(4)
    head.left.right =  Node(5)
    head.right.left =  Node(6)
    head.right.right =  Node(7) 
    print(isBalance(head))
main()



class Node:
    def __init__(self, data: int) -> None:
        self.val = data
        self.left = None
        self.right = None

'''
给定head, 返回任何两个节点之间的最大距离
'''
#return (最大距离，高度)
# 树型dp解法
# def process(head: Node) ->tuple:
#     if not head : return 0, 0

#     left_info = process(head.left)
#     right_info = process(head.right)
#     height = max(left_info[1], right_info[1]) + 1
#     max_distance = max(max(left_info[0], right_info[0]), (left_info[1]+right_info[1]+1))

#     return max_distance, height


'''
给定head, 返回最大搜索二叉子树的节点个数
'''
#返回值（isall_bst, max_subsize, imax, imin）
# isall_bst  以head开头整颗树是否二叉搜索树
# max_subsize 二叉搜索子树节点个数
# imax 左右子树的最大值
# imin 左右子树的最小值
# def process(head: Node)->tuple:
#     if not head: return None
   
#     left_info = process(head.left)
#     right_info = process(head.right)

#     #这种可能性是最大子树不包含头head
#     imin = imax = head.val

#     imin = min(imin, (imin if not left_info else left_info[3]))
#     imin = min(imin, (imin if not right_info else right_info[3]))

#     imax = max(imax, (imax if not left_info else left_info[2]))
#     imax = max(imax, (imax if not right_info else right_info[2]))

#     max_subsize = max((0 if not left_info else left_info[1]), (0 if not right_info else right_info[1]))
    
#     isall_bst = False # 默认表示包含head的整颗树不是二叉搜索树
#     #这种可能性是最大二叉搜索子树包括头head(左右子树整体必须是二叉搜索树, 并且左数最大值<head.val, 右数最小值>head.val)
#     if (True if not left_info else left_info[0]) and (True if not right_info else right_info[0]) and \
#         (True if not left_info else (left_info[2] < head.val)) and (True if not right_info else (right_info[3] > head.val)):

#         isall_bst = True
#         max_subsize = (0 if not left_info else left_info[1]) + (0 if not right_info else right_info[1]) + 1

#     return isall_bst, max_subsize, imax, imin

'''
派对最大happy值:
整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，
除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。
这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：
1.如果某个员工来了，那么这个员工的所有直接下级都不能来。
2.派对的整体快乐值是所有到场员工快乐值的累加。
3.你的目标是让派对的整体快乐值尽量大。
给定一棵多叉树，请输出派对的最大快乐值。
'''
class Employee:
    def __init__(self, happy: int) -> None:
        self.happy = happy
        self.subordinates = None #直属下级的节点， 
#(y, n)
# y 子树头节点来的情况下最大快乐值
# n 子树头节点不来的情况下最大快乐值
def process(head: Employee) ->tuple:
    if not head.subordinates: return head.happy, 0
    yes = head.happy
    no = 0
    for i in head.subordinates:
        info = process(i)
        yes += info[1] # 头节点来，直接下属不来情况下的最大happy
        no += max(info[0], info[1]) # 头节点不来，直接下属来与不来情况下的happy,求最大值
    return yes, no

def main():
    head =  Node(1)
    head.left =  Node(2)
    head.right =  Node(3)
    head.left.left =  Node(4)
    head.left.right =  Node(5)
    head.right.left =  Node(6)
    head.right.right =  Node(7) 
    print(process(head))
main()

